package com.company.Tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}13:37
 */
public class Huffmantree{
    public static void main(String[] args) {
        int arr[] = {13,7,8,3,29,6,1};
        preOrder(creatHuffmanTree(arr));
    }

    //编写一个前序遍历的方法
    public static void preOrder(Node node){
        if (node!=null){
            node.preOrder();
        }
    }

    //创建赫夫曼树
    public static Node creatHuffmanTree(int[] arr){
        //遍历arr数组
        //将arr的每个元素构成一个Node
        //将Node放入ArrayList中
        List<Node> nodes = new ArrayList<>();
        for (int value:arr){
            nodes.add(new Node(value));
        }
        while (nodes.size()> 1){
            Collections.sort(nodes);
            Node left = nodes.get(0);
            Node right = nodes.get(1);

            Node finalNode = new Node(left.value+right.value);
            finalNode.left=left;
            finalNode.right=right;
            nodes.add(finalNode);
            nodes.remove(left);
            nodes.remove(right);
        }
        Collections.sort(nodes);
        return nodes.get(0);
    }
    static class Node implements Comparable<Node>{
        int value;
        Node left;//左子结点
        Node right;

        public Node(int value) {
            this.value = value;
        }

        public void preOrder(){
            System.out.println(this);
            if (this.left!=null){
                this.left.preOrder();
            }
            if (this.right!=null){
                this.right.preOrder();
            }
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }

        @Override
        public int compareTo(Node o) {
            return this.value-o.value;
        }
    }
}


